1382. Balance a Binary Search Tree

給定一個二叉搜索樹 (BST)，你的目標是將其轉換為一棵高度平衡的二叉搜索樹。高度平衡的意思是：一棵二叉樹的每個節點的兩棵子樹的高度差不超過 1。

解題思路

1. 中序遍歷：首先，利用中序遍歷將二叉搜索樹轉換為一個排序的節點列表。這是因為中序遍歷的結果會保留二叉搜索樹的順序性質。
2. 構建平衡樹：使用中序遍歷結果的排序列表來遞歸地構建一棵平衡二叉搜索樹。具體方法是：
   • 選取排序列表的中間節點作為根節點。
   • 中間節點左邊的節點用來構建左子樹，右邊的節點用來構建右子樹。
   • 這樣不斷遞歸地選取中間點，就可以保證每個子樹都是高度平衡的。

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        # Step 1: 中序遍歷，獲取排序後的節點列表
        def inorderTraversal(node):
            if not node:
                return []
            return inorderTraversal(node.left) + [node] + inorderTraversal(node.right)
        
        sorted_nodes = inorderTraversal(root)
        
        # Step 2: 根據排序後的節點列表構建平衡二叉樹
        def buildBalancedBST(nodes):
            if not nodes:
                return None
            mid = len(nodes) // 2
            root = nodes[mid]
            root.left = buildBalancedBST(nodes[:mid])
            root.right = buildBalancedBST(nodes[mid+1:])
            return root
        
        return buildBalancedBST(sorted_nodes)

時間複雜度

• 中序遍歷二叉搜索樹的時間複雜度是 O(n)，其中 n 是樹中的節點數。
• 構建平衡二叉樹的過程也是 O(n)，因此總的時間複雜度是 O(n)。

關鍵點

• 中序遍歷： 中序遍歷將二叉搜索樹轉換為有序的節點列表，這是平衡樹構建的基礎。
• 遞歸構建平衡樹： 選取列表中間的節點作為根節點，確保左右子樹的節點數目大致相等。